package algotithm.weekendrace.leetcode240.test3;

import java.util.LinkedList;

/**
 * @author 25068
 * @Date 2021/5/9 22:00
 * @Title 5752. 子数组最小乘积的最大值
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,3,2};
        int maxSumMinProduct = solution.maxSumMinProduct(nums);
        System.out.println(maxSumMinProduct);
    }

    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        LinkedList<Integer> left = new LinkedList<>();
        int[] l = new int[n];
        for(int i = 0; i < n; i++) {
            while(!left.isEmpty() && nums[left.getLast()] >= nums[i]) {
                left.removeLast();
            }
            l[i] = left.isEmpty() ? -1 : left.getLast();
            left.add(i);
        }

        LinkedList<Integer> right = new LinkedList<>();
        int[] r = new int[n];
        for(int i = n-1; i >= 0; i--) {
            while(!right.isEmpty() && nums[right.getLast()] >= nums[i]) {
                right.removeLast();
            }
            r[i] = right.isEmpty() ? n : right.getLast();
            right.add(i);
        }

        long[] sum = new long[n+1];
        for(int i = 1; i <= n; i++) {
            sum[i] = sum[i-1] + nums[i-1];
        }

        long ans = 0, MOD = (long)(1e9 + 7);
        for(int i = 0; i < n; i++) {
            int idx1 = l[i], idx2 = r[i];
            ans = Math.max(ans, (sum[idx2] - sum[idx1 + 1]) * nums[i]);
        }

        return (int)(ans % MOD);
    }
}
